package niuke;

import leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author wangmaolin1
 * @date 2022/7/30 2:17 下午
 */
public class _45二叉树打印 {
    /**
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    public static int[][] threeOrders(TreeNode root) {
        // write code here
        int[][] result = new int[3][];

        List<Integer> pre = new ArrayList<>();
        List<Integer> in = new ArrayList<>();

        List<Integer> post = new ArrayList<>();

        if (root != null) {
            TreeNode temp = root;
            preOrder(temp, pre);
            inOrder(temp, in);
            postOrder(temp, post);
        }
        result[0] = new int[pre.size()];
        result[1] = new int[in.size()];
        result[2] = new int[post.size()];
        if (pre.size() > 0) {
            for (int i = 0; i < pre.size(); i++) {
                result[0][i] = pre.get(i);
            }
        }
        if (in.size() > 0) {
            for (int i = 0; i < in.size(); i++) {
                result[1][i] = in.get(i);
            }
        }
        if (post.size() > 0) {
            for (int i = 0; i < post.size(); i++) {
                result[2][i] = post.get(i);
            }
        }
        return result;
    }

    private static void preOrder(TreeNode root, List<Integer> preArr) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        int i = 0;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                preArr.add(root.val);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;
        }
    }

    private static void inOrder(TreeNode root, List<Integer> preArr) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        int i = 0;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            preArr.add(root.val);
            root = root.right;
        }
    }

    private static void postOrder(TreeNode root, List<Integer> preArr) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        int i = 0;
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.right == null || root.right.equals(pre)) {
                preArr.add(root.val);
                pre = root;
                root = null;
            } else {
                root = root.right;

            }
        }
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(0);
        treeNode.left = new TreeNode(1);
        treeNode.right = new TreeNode(2);
        treeNode.right.left = new TreeNode(3);
        treeNode.right.right = new TreeNode(4);
        int[][] ints = threeOrders(treeNode);
        System.out.println(ints);
    }
}
